package com.hdu.other.dp.intervalDp;


public class lc1039 {
    class Solution {
        public int minScoreTriangulation(int[] values) {
            int len = values.length;
            int[][] dp = new int[len][len];
            for (int i = 0; i < len; i++) {
                for (int j = 0; j < len; j++) {
                    dp[i][j] = -1;
                }
            }
            return f(values, 0, len - 1, dp);
        }

        int f(int[] values, int l, int r, int[][] dp)
        {
            int len = r - l + 1;
            if (len <= 2) {
                return 0;
            }
            if (dp[l][r] != -1) {
                return dp[l][r];
            }
            int ans = Integer.MAX_VALUE;
            for (int i = l + 1; i < r; i++) {
                int curAns = f(values, l, i, dp) + f(values, i, r, dp) + values[l] * values[i] * values[r];
                ans = Math.min(ans, curAns);
            }
            return dp[l][r] = ans;
        }
    }
}
